#
# @lc app=leetcode.cn id=494 lang=python
#
# [494] 目标和
#

# @lc code=start
class Solution(object):
    def findTargetSumWays(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: int
        """
        if sum(nums)< abs(target):
            return 0
        if (sum(nums)+target) % 2 != 0:
            return 0
        left = (sum(nums)+target)/2
        dp = [0]*(left+1)
        dp[0] = 1

        for num in nums:
            for j in range(left, num-1, -1):
                dp[j] += dp[j-num]
        return dp[-1]

        
# @lc code=end

